// 最小支配集
// https://www.luogu.com.cn/problem/P2016

int n;
int f[maxn][2];
vector<int> tr[maxn];
// f[now][1] = sum(min(f[sub][0], f[now][1])) + a[now]
// f[now][0] = sum(f[sub][1])
int dfs(int now, int fa, bool ch) {
    if (f[now][ch]) return f[now][ch];
    int cnt = ch;
    if (ch) {
        for (auto &p : tr[now])
            if (p != fa)
                cnt += min(dfs(p, now, 0), dfs(p, now, 1));
    } else {
        for (auto &p : tr[now])
            if (p != fa)
                cnt += dfs(p, now, 1);
    }
    return f[now][ch] = cnt;
}
